/**
 * 给定字符串，找满足条件的子串：
 * 1. 子串中出现的字母，每种字母恰好出现limit次
 * 2. 相邻字母差的绝对值不超过2
 * 注意到第一个条件实际上指示了子串的长度只有可能有26种，从limit到26limit。
 * 因此对每个可能的长度直接验证即可，O(26^2*N)
 * 至于第2个条件，可以事先分段
 */
class Solution {
public:
    int countCompleteSubstrings(string word, int limit) {
        int n = word.length();
        int k = 0;
        int ans = 0;
        while(1){
            int t = 1;
            while(k + t < n and abs(word[k+t] - word[k+t-1]) <= 2){
                ++t;
            }
            ans += f(word, k, k + t - 1, limit);
            if((k += t) == n) break;
        }    
        return ans;
    }

    int f(const string & s, int a, int b, int limit){
        int n = b - a + 1;
        int ans = 0;
        for(int i=1;i<=26;++i){
            int len = limit  * i;
            if(len > n) break;
            ans += g(s, a, b, limit, len);
        }     
        return ans;
    }

    int g(const string & s, int a, int b, int limit, int len){
        array<int, 256> cnt{0};
        for(int i=a;i<len+a;++i) ++cnt[s[i]];

        int ans = 0;
        for(int i=len+a;i<=b;++i){
            if(check(cnt, limit)) ++ans;
            ++cnt[s[i]];
            --cnt[s[i - len]];
        }
        if(check(cnt, limit)) ++ans;
        return ans;
    }

    bool check(const array<int, 256> & cnt, int limit){
        for(int i='a';i<='z';++i)if(cnt[i] != 0 and cnt[i] != limit) return false;
        return true;
    }
};